package part_2;

import java.util.ArrayList;

/**
 * this class implements the greedy algorithm for solving the tsp problem
 */
public class Greedy_TSP_alg
{
	/**
	 * this function run the greedy algorithm for the tsp problem
	 * @param cities_locs - an array for holding the positions of the cities in the tsp problem
	 * @param best - the best route for this specific tsp problem
	 */
	public void run_alg(ArrayList<int[]> cities_locs, ArrayList<Integer> best) 
	{
		ArrayList<Integer> sol=new ArrayList<Integer>();
		// adding the first city
		sol.add(1);
		ArrayList<Integer> not_picked_yet=new ArrayList<Integer>();

		// initiating the not picked array to all the cities
		for(int i=1;i<cities_locs.size();i++)
			not_picked_yet.add(i+1);
		
		// as long as the route isn't complete keep running
		while(!not_picked_yet.isEmpty())
		{
			int closest_city=-1;
			double closest_dist=1000000;

			// for every city left to go too
			for(int i=0;i<not_picked_yet.size();i++)
			{
				int[] a=cities_locs.get(sol.get(sol.size()-1)-1);
				int[] b=cities_locs.get(not_picked_yet.get(i)-1);
				// calculating the distance between the current city and this optional city
				double cur_dist=Math.sqrt(Math.pow(a[0]-b[0],2)+Math.pow(a[1]-b[1],2));
				// the case that this optional route is closer than the current closest one 
				if(cur_dist<closest_dist)
				{
					// keeping the closest city
					closest_dist=cur_dist;
					closest_city=not_picked_yet.get(i);
				}
			}

			// adding this city to the solution route
			sol.add(closest_city);
			not_picked_yet.remove(new Integer(closest_city));
			
		}

		System.out.println("best sol is "+best);
		System.out.println("our sol is "+sol);
		System.out.println("our greedy price "+calcPrice(sol, cities_locs));
		System.out.println("best price "+calcPrice(best, cities_locs));
		System.out.println("difference "+(calcPrice(sol, cities_locs)-calcPrice(best, cities_locs)));
	}

	/*
	 * this function calculate the weight of the given solution of the tsp problem
	 * @param sol - a given solution to the tsp problem
	 * @param cities_locs - an array for holding the positions of the cities in the tsp problem
	 * @return - the weight of the given solution
	 */
	private double calcPrice(ArrayList<Integer> sol,ArrayList<int[]> cities_locs)
	{
		
		double price = 0.0;
		double cur_dist;
		int[] a;
		int[] b;
		// for every two cities in the route 
		for(int i=0;i<sol.size()-1;i++)
		{
			a=cities_locs.get(sol.get(i)-1);
			b=cities_locs.get(sol.get(i+1)-1);
			
			// calculate the distance between those two cities
			cur_dist=Math.sqrt(Math.pow(a[0]-b[0],2)+Math.pow(a[1]-b[1],2));
			// and add this distance to the total route weight
			price +=  cur_dist;
		}
		
		// one more iteration because this is a circle (according to the tsp problem)
		a=cities_locs.get(sol.get(0)-1);
		b=cities_locs.get(sol.get(sol.size()-1)-1);
		price += Math.sqrt(Math.pow(a[0]-b[0],2)+Math.pow(a[1]-b[1],2));
		return price;
	}
}
